尚硅谷 韩顺平

1
本课程是使用Java来讲解数据结构和算法，考虑到数据结构和算法较难，授课采用图解加算法游戏的方式. 内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)等

image-20190619073746578

1 稀疏数组

image-20190619111425567

image-20190619111502851

image-20190619111543993

image-20190619111716242

image-20190619111809157

image-20190619112018355

image-20190619112247143

image-20190619112540711

1.1 原始二维数组转为稀疏数组

遍历原始的二维数组 得到非0的数字sum个

根据sum 创建稀疏数组sparseArr int [sum+1] [3]

将二维数组非0 的数字存到稀疏数组里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package DataStructure.SparseArray;

/**
 * @description:
 * @author: apple
 * @date: 2019-06-25 09:35
 */
public class SpareseArray {
    public static void main(String[] args) {
        //step1 : 创建一个原始的二维数组
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);//%d 打印十进制整数
            }
            System.out.println();
        }
        //step2： 将二维数组转换成稀疏数组
        //step2.1:  先遍历二维数组 得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr.length; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        System.out.println("sum非0个数为" + sum);
        //step3:创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        //step3.1 给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //step3.2 ⭐️⭐️⭐️遍历二维数组 将非0的值 1 2 存放到稀疏数组中⭐️⭐️⭐️⭐️⭐️⭐️
        int count = 0; //count用于记录是第几个非0的数据
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr.length; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        //step3.3: 输出稀疏数组的格式
        for (int[] arr : sparseArr) {
            for (int row : arr) {
                System.out.printf("%d\t", row);
            }
            System.out.println();
        }
    }
}

1.2稀疏数组转二维数组

先读取稀疏数组的第一行 根据第一行的数据 创建原始的二维数组

在读取稀疏数组后几行的数据 并赋给原始的二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
        //1 先读取稀疏数组的第一行 根据第一行的数据 创建原始的二维数组
        int chessArr2[][] = new int[sparseArr[0][1]][sparseArr[0][1]];
        //2 在读取稀疏数组后几行的数据 并赋给原始的二维数组
        
        
        for (int i = 1; i < sparseArr.length; i++) {
            //3 输出后的二维数组 ⭐️⭐️⭐️⭐️⭐️⭐️⭐️
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️
        
        
        for (int[] chess2 : chessArr2) {
            for (int row : chess2) {
                System.out.printf("%d\t", row);
            }
            System.out.println();
        }
    }

2 队列的应用场景和介绍

image-20190625105216355

image-20190625112719188

image-20190625112902996

快速排序

image-20190818190007241

image-20190818190210855

image-20190818202711898

1
 
1

image-20190818220506429

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package Day01;

import java.util.Arrays;

public class QuickSortr {

    public static void main(String[] args) {
        int[] arr = {-9, 78, 15, 11, 23, -567, 70, 69, 18};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    //left 左索引 右索引
    public static void quickSort(int[] arr, int left, int right) {
        int l = left; //左下标
        int r = right;//右下标
        //pivot中轴
        int pivot = arr[(left + right) / 2];
        int temp = 0;//临时遍历 作为交换使用
        //while循环的目的是让比pivot值小的放到左边
        //比pivot的值放到右边
        while (l < r) {

            //在pivot的左边一直找，找到一个大于等于pivot的值才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到一个小于等于pivot的值才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //如果l>=r 说明pivot的两边左右的值 已经按照
            //左面全部是小于等于pivot的值，右边全部是大于等于pivot的值
            if (l >= r) {
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交换完后 发现arr[l]==pivot的值
            // 如果arr[l]==pivot的值相等 前移动 r --
            if (arr[l] == pivot) {
                r -= 1;//画图  退出循环while(l<r)
            }
            //如果交换完后 发现arr[r]==pivot的值
            // 如果arr[r]==pivot的值相等  后移动l++
            if (arr[r] == pivot) {
                l += 1;
            }
        }


        //~~~~向左递归~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        //[-567, -9, 0, 23, 78, 70]
        //如果l==r 必须l++ r--否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归????????left=? r=?
        if (left < r) {    left右移过去了
            quickSort(arr, left, r);
        }
        //~~~~向右递归~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        //[-567, -9, 0, 23, 78, 70]
        if (right > l) {
            quickSort(arr, l, right);
        }

    }
}

归并排序

image-20190819143737622

image-20190819143905544

image-20190819144139594

image-20190819164010946

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package Day01;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("归并排序后" + Arrays.toString(arr));
        //int mid = arr.length / 2;
        //merger(arr, 0, mid, arr.length - 1, temp);
    }

    //分+合
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间的索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);

            //⭐️
            //到合并时候
            merger(arr, left, mid, right, temp);

        }

    }


    /**
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void merger(int[] arr, int left, int mid, int right, int[] temp) {

        int i = left;//初始化i ,表示左边有序序列的初始索引

        int j = mid + 1;//初始化j 表示右边有序序列的初始索引

        int t = 0;  //指向temp数组的初始索引

        //（一）
        //先把左右两边（有序）的数据按照规则 填充到temp数组中
        //直到左右两边的有序序列 有一边处理完毕为止

        while (i <= mid && j <= right) { //继续
            //如果左边的有序序列的当前元素小于等于右边的有序序列的当前元素
            //即将左边的当前元素  拷贝到temp数组中
            //然后t++ i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之(arr[i] >= arr[j])
                //将右边有序序列的当前元素 填充到temp中
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }

        }


        //（二）
        //把剩余数据的一边的数据依次全部填充到temp

        while (i <= mid) {
            //左边的有序序列还有剩余的元素 就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            //右边的有序序列还有剩余的元素 就全部填充到temp
            temp[t] = arr[j];
            j += 1;
        }


        //（三） ❓❓❓❓❓❓❓❓❓❓❓❓❓
        //将temp数组的元素拷贝到arr
        //并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;//第一次 合并时
        //  第一次合并 tempLeft=0 right=1 tempLeft=2 right=3 tLl=0
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

马士兵 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package sortdemo;

import java.util.Arrays;

public class TestMerger {
    public static void main(String[] args) {
        int[] arr = {1, 4, 7, 8, 3, 6, 9};
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int left, int right) {
        if (left == right) {
            int mid = left + (right - left) / 2;
            sort(arr, left, mid);
            sort(arr, mid + 1, right);
            merge(arr, left, mid + 1, right);
        }

    }

    public static void merge(int[] arr, int leftPtr, int rightPtr, int rightBound) {
        int mid = rightPtr - 1;
        int[] temp = new int[rightBound - leftPtr + 1];
        int i = leftPtr;
        int j = rightPtr;
        int k = 0;

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= rightBound) {
            temp[k++] = arr[j++];
        }


        for (int m = 0; m < temp.length; m++) {
            arr[leftPtr + m] = temp[m];
        }
    }

}

冒泡排序

image-20190824074127128

image-20190824074229714

image-20190824075400900

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        for (int i = 0; i < arr.length - 1; i++) {

            //第一趟排序就是把最大的数排在最后
            int temp = 0;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //如果前面的数比后面的大 交换

                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));

        }
    }
}

选择排序

image-20190824075824118

image-20190824080017228

image-20190824083316650

image-20190824083524042

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package Day01;

import java.util.Arrays;

public class SelectSort {

    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println("排序前" + arr);
        slelctSort(arr);
    }


    //选择排序
    public static void slelctSort(int arr[]) {
        //第一轮
        //原始数组 101 34 119 1
        //第一轮排序 1 34 119 101


        for (int i = 0; i < arr.length - 1; i++) {


            //第一轮 最小值和最小值的索引
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {//说明假定的最小值 并不是最小
                    min = arr[j];//重置min
                    minIndex = j;//重置minIndex
                }
            }
            //将最小值 放在arr[0],即交换 原来存放arr最小值的值放arr[0]
            arr[minIndex] = arr[i];
            arr[i] = min;
            System.out.println("第一轮后～～～");
            System.out.printf(Arrays.toString(arr));

        }
    }
}

二分查找